package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 单边快排
 * @version: 1.0
 */
public class UnilateralSort {

    /*
     * 时间复杂度: 最好O(nlogn)  最坏O(n^2)  平均O(logn)
     * 空间复杂度: O(logn)
     */
    public static int[] quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
        return arr;
    }

    //递归
    private static void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(arr, left, right);//p为基准点
        quick(arr, left, p - 1);
        quick(arr, p + 1, right);
    }

    //分区
    private static int partition(int[] arr, int left, int right) {
        int pv = arr[right];//基准点元素的值
        int i = left;
        int j = left;
        while (j < right) {
            if (arr[j] < pv) {
                //找到比基准点小的元素
                if (i != j) {
                    swap(arr, i, j);
                }
                i++;
            }
            j++;
        }
        swap(arr, i, right);
        return i;
    }


    //交换
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
